# 1 ----------------- To Find Closure ----------------
from  prettytable import PrettyTable

def closure(I, nonT):
    """求项目集I的闭包"""
    J = I
    for item in J:
        index = item[1].index('.')   # 求'.'在产生式右部位置下标
        # print("index:",index)
        if index < (len(item[1]) - 1) and item[1][index + 1] in nonT:
            # 如果'.'不在最后产生式最右端 && '.'的下一个符号是非终结符B的话，需要把'.'右边的终结符B->.γ加入项目集I
            # item[1][index+1]表示的是'.'后面的非终结符
            for production in nonT[item[1][index + 1]]:
                # 依次遍历这个非终结符的每个产生式子
                if [item[1][index + 1], str('.') + str(production)] not in J:
                    # 如果这个产生式不在这个项目集中，把这个非终结符的产生式加入该项目集中
                    J.append([item[1][index + 1], str('.') + str(production)])
    # 返回求闭包后的项目集
    return J
# ------------------- Ends --------------------------------


# 2. --------------- Set of Canonical Items ---------------------

state = []  # 存储状态转移
I = []  # 存储所有项目

def setOfItems(start, nonTer, ter):
    # 增广文法
    I.append(closure([['start', '.' + start + '#']], nonTer))
    # 打印增广文法后的I0项目集
    print("I0:\n", I)
    # ter加上非终结符
    ter += list(nonTer.keys())
    print("list of inputs : ", ter)

    for conI in I:
        # print("conI:", conI)
        # 遍历每一个符号（非终结符和终结符）
        for grammar in ter:
            # 如果符号是#，跳过当前循环
            if (grammar is '#'):
                continue
            # 如果符号不是#，执行下面语句
            # print("grammar : ",grammar)
            goto = False
            goto1 = False
            shift = False
            shift1 = False
            reduce = False
            close = []
            # 遍历当前项目集中每一元素
            for item in conI:
                # print("item  : ", item)
                if item[1].index('.') < (len(item[1]) - 1) and item[1][item[1].index('.') + 1] is grammar:
                    # 如果'.'不在最后产生式最右端 && '.'的下一个符号是当前的grammar
                    # 把所有匹配的产生式中'.'偏移到匹配的grammar后面，存在close中
                    close.append([item[0], item[1][:item[1].index('.')] + grammar + '.' + item[1][item[1].index('.') + 2:]])
                # else:
                # print(item)

            # print("close : ", close)
            # 利用闭包函数closure求close集合的闭包
            l = closure(close, nonTer)

            if len(l) == 0:
                continue

            # 如果当前的符号是非终结符,标记goto1为true
            if grammar in nonTer.keys():
                goto1 = True
            # 如果当前的符号是终结符,
            else:
                shift1 = True

            # 如果新生成的项目集在I中不存在
            if l not in I:
                if goto1:
                    # I.index(conI) + 1 是原项目集在I中的位置标号，len(I) + 1 是新生成的项目集序号
                    state.append(['g', I.index(conI) + 1, len(I) + 1, grammar])
                    goto = True
                elif shift1:
                    shift = True
                    state.append(['s', I.index(conI) + 1, len(I) + 1, grammar])
                # 将新项目集加到I中
                I.append(l)
            # 如果新生成的项目集在I中已经存在
            else:
                if goto1:
                    goto = True
                    state.append(['g', I.index(conI) + 1, I.index(l) + 1, grammar])
                elif shift1:
                    shift = True
                    state.append(['s', I.index(conI) + 1, I.index(l) + 1, grammar])


# -----------------------------------------------------------------


# 3. -----------------Create a Parse Table ------------------------
reduce = []
accept = -1

def toReduce(rule, accept, start):
    s = ['start', start + '.#']
    for parState in I:
        # 遍历I中每个项目集parState
        if s in parState:
            # 如果该项目集中有s,说明该项目集
            # print("here;")
            accept = I.index(parState)
        for item in parState:
            # 遍历该项目集中的每一个产生式
            if (item in rule):
                # 如果该产生式是可归约的
                reduce[I.index(parState)].append(rule.index(item))  # reduce[i]表示第i个项目集中含有第几个可规约式
    return accept  # 返回第几个项目集中有accept


# ------------------------------------------------------------------


# 4. --------------------- To Parse --------------------------------
symbolMap = dict()  # 存放符号的下标
parseTable = []     # 二维矩阵预测表

def createParseTable(ter, Follow, rule):
    """构造预测表"""

    for i in state:
        # 遍历每一个状态转移，填写Action表中的状态转移s和Goto的预测表的g
        parseTable[i[1] - 1][symbolMap[i[3]]] = i[0] + str(i[2] - 1)  # parseTable 是一个二维矩阵

    # 填写acc
    parseTable[accept][symbolMap['#']] = 'acc'

    # 遍历每个项目集，查看是否存在可归约的式子
    for i in reduce:
        # 若存在可规约的式子
        if len(i) > 0:
            for j in Follow[rule[int(i[0])][0]]:
                # 将可归约的产生式左边的非终结符A的follow集合中所有的非终结符a（相应列）都加上规约动作r1
                parseTable[reduce.index(i)][symbolMap[j]] = 'r' + str(i[0])


# (i) Stack -------------------------
class Stack:
    def __init__(self):
        self.__storage = []

    def isEmpty(self):
        return len(self.__storage) == 0

    def push(self, p):
        self.__storage.append(p)

    def pop(self):
        return self.__storage.pop()

    def top(self):
        return self.__storage[len(self.__storage) - 1]

    def length(self):
        return len(self.__storage)

    def __str__(self):
        # 翻转栈
        return 'stack [{}]'.format(', '.join([str(i) for i in self.__storage]))


# --------------------Stack Defn ENDS ------------------------------------------
def parseString(rule, string):
    """

    :param rule:
    :param string:
    :return:
    """

    
    parse_list = []
    parse_table = PrettyTable()
    parse_table.field_names = ["stack", "当前输入", "动作"]
    index = 0     # index指针指向字符串中的哪个字符
    flag = False  # flag用来字符串是否合法
    st = Stack()  # 栈st存放状态和输入符
    st.push('0')  # 栈先存入0

    # 依次移动指向字符串的指针
    while index < len(string):

        # 根据栈顶和当前输入符号查预测表得到当前动作v
        v = parseTable[int(st.top())][symbolMap[string[index]]]
        # 添加值打印列表
        parse_list.append([st.__str__(), string[index:], v])
        # 判断当前动作
        c = v[0]
        # 查看当前动作后面的序号pt
        pt = v[1:]

        # 1.若是accept
        if c is 'a':
            # print(parse_table)
            flag = True  # acc表示当前输入字符串合法
            break

        # 2.若是reduce规约
        if c is 'r':
            pt = int(pt)
            # l是可归约式子的右部的长度
            l = len(rule[pt][1])
            l *= 2
            l -= 2  # '.' is also considered
            if (l >= st.length()):
                break
            else:
                # 进行规约操作
                for i in range(l):
                    st.pop()            # 将匹配的规约式右部出栈
                top = int(st.top())     # top出栈后的状态序号
                st.push(rule[pt][0])    # 将匹配的规约式左边非终结符入栈
                st.push(parseTable[top][symbolMap[st.top()]][1:])  # 查找goto表,将查找到的值入栈

        # 3.若是shift移进
        elif c is 's':
            pt = int(pt)
            st.push(string[index])  # 将index指向的字符入栈
            st.push(str(pt))        # 同时将s后面的序号也入栈
            index += 1              # 此时将index指针右移

        # 4.分析错误
        else:
            print("Error!")
            break

    for i in parse_list:
        parse_table.add_row(i)
    print(parse_table)

    # 返回分析是否正确的标志
    return flag


# ------------------------------------------------------------------


# -----------------------First and Follow --------------------------
First = dict()  # 用字典存first集合
Follow = dict()  # 用字典存follow集合


# (i) ------ First ---------
def first4pro(str):
    fir = []
    flag = False
    for i in str:
        if ('ε' not in First[i]):
            fir += First[i]
            flag = True
            break
        else:
            fir += First[i]
            fir.remove('ε')
    if (not flag):
        fir += ['ε']

    return fir


def first(nT, nonT, checked):
    if checked[nT]:
        return
    else:
        for i in nonT[nT]:
            # print("production" ,i)
            last = True
            for j in i:
                if (j is nT):
                    continue
                if (checked[j]):
                    if ('ε' not in First[j]):
                        First[nT] += First[j]
                        last = False
                        break
                    else:
                        First[nT] += First[j]
                        First[nT].remove('ε')
                else:
                    first(j, nonT, checked)
                    if ('ε' not in First[j]):
                        First[nT] += First[j]
                        last = False
                        break
                    else:
                        First[nT] += First[j]
                        First[nT].remove('ε')
            if (last):
                First[nT].append('ε')
        checked[nT] = True


def createFirst(ter, nonT):
    checked = dict()
    # --- initialising the checked
    for i in ter:
        checked[i] = True
        First[i] = [i]
    for i in list(nonT.keys()):
        checked[i] = False
        First[i] = []

    # ---- first --------
    for i in list(nonT.keys()):
        if (not checked[i]):
            first(i, nonT, checked)
            First[i] = list(set(First[i]))


# (ii) ------- Follow------------
def follow(nT, nonT, checked):
    if checked[nT]:
        return
    else:
        for i in nonT.keys():
            pro = list(nonT[i])
            for j in pro:
                # print(i," -- > ",pro , " to check ",nT , " from : ", j)
                if nT in j:
                    ind = j.index(nT) + 1
                    while ind < len(j):
                        if 'ε' not in First[j[ind]]:
                            Follow[nT] += First[j[ind]]
                            break
                        else:
                            Follow[nT] += First[j[ind]]
                        ind += 1
                    if ind == len(j):
                        if i == nT:
                            continue
                        follow(i, nonT, checked)
                        Follow[nT] += Follow[i]
        checked[nT] = True


def createFollow(ter, nonT, S):
    checked = dict()
    # --- Initialising the checked ---
    for i in list(nonT.keys()):
        checked[i] = False
        Follow[i] = []
    Follow[S] = ['#']

    # calling the follow

    for i in list(nonT.keys()):
        if (not checked[i]):
            follow(i, nonT, checked)
            if (len(Follow[i]) == 0):
                checked[i] = False
    for i in list(nonT.keys()):
        Follow[i] = list(set(Follow[i]))
        if ('ε' in Follow[i]):
            Follow[i].remove('ε')

    '''for i in list(nonT.keys()):
        if( not checked[i]):
            follow(i,nonT,checked)
            Follow[i] = list(set(Follow[i]))
            if(len(Follow[i]) == 0):
                checked[i] = False
       '''


# ------------------------ First and Follow ends --------------------


# ---------------------------- Driver Program -------------------------
# 读文件
with open("data.txt", "r") as f:
    data = []
    for line in f.readlines():
        data.append(line.strip('\n'))  # 去掉列表中每一个元素的换行符
input_list=[]
for i in data:
    input_list.append(i.split(':')[1])

terminals = []  # 终结符用列表存储
nonTerminals = dict()  # 非终结符用字典存储
mode=int(input("read File(input 1) or input by yourself(input 2):"))
S=None
if mode==2:
    terminals = input("Enter Terminals (|) : ").split("|")  # 依次输入终结符，并使用split函数将各个候选分割开放入terminals列表
    n = int(input("No. of Non - Terminals  : "))  # 输入非终结符个数

    for i in range(n):
        ch = input("NonTerminals : ").strip()  # 输入非终结符
        rules = input("Productions (|) : ").split("|")  # 输入产生式右部
        nonTerminals[ch] = rules  # 字典存储每个非终结符的各个候选
    S = input("Start Symbol :  ")  # 输入文法开始符号
elif mode==1:
    terminals=input_list[0].strip().split("|")
    n=int(input_list[1].strip())

    for i in range(n):
        ch=input_list[2+2*i].strip()
        rules=input_list[3+2*i].strip().split("|")
        nonTerminals[ch]=rules
    S=input_list[-1].strip()
else:
    exit(3)
# --- Old Rules-------
terminals += ['#']  # 终结符加一个

# 打印各个产生式
print("Productions : ")
for i in nonTerminals.keys():
    print(i, "->", end='')
    for j in nonTerminals[i]:
        print(j, end='|')
    print()

# 构造DFA
setOfItems(S, nonTerminals, terminals)
# 打印终结符和非终结符
print("Symbols:", terminals)
# 打印项目集
print("canonicals Items in DFA : ")
for count, i in enumerate(I):
    print(count, i)

# 打印DFA中的状态转移
print("state Transitions : ")
for count, i in enumerate(state):
    print(count + 1, i)

# 可以规约的式子
rule = []
accept = -1
for i in nonTerminals.keys():
    for j in nonTerminals[i]:
        rule.append([i, j + str('.')])
print('Reduced rule :')
for i in rule:
    print(i)

# -------  To find the reduction rules - -- - -- ---
reduce = [[] for i in range(len(I))]
accept = toReduce(rule, accept, S)

print("reduce")
for count, i in enumerate(reduce):
    print(count + 1, i)

print("accept : ", accept + 1)

# ---  - - - parse Table - -- -- - -- -- - -- - - -- -
symbols = []
symbols += terminals

for count, i in enumerate(symbols):
    symbolMap[i] = count
print("symbols: ", symbols)

# 预测表初始化,len(symbols)是所有的终结符和非终结符的数目，len(I)是所有项目集的数目
parseTable = [['-' for i in range(len(symbols))] for j in range(len(I))]


for i in nonTerminals.keys():
    terminals.remove(i)

# -------------- First and Follow ----------
# 求并打印非终结符的first 和 follow 集合
createFirst(terminals, nonTerminals)  # 求first集合

createFollow(terminals, nonTerminals, S)  # 求follow集合

print("{}\t\t\t{}\t\t\t\t\t\t{}".format('NonTerminals', 'First', 'Follow'))
for i in nonTerminals.keys():
    print("{}\t\t\t\t{}\t\t\t{}".format(i, First[i], Follow[i]))

# ----------------------Done--------------------------------
# 构造预测表
createParseTable(terminals, Follow, rule)

# ---Parse Table-----
print('\t\t\t\tParse Table')
# 打印表头符号
print(" \t\t", end='')
for i in symbols:
    print(i, end='\t')
print()
# 打印表中每个元素的值
for count, j in enumerate(parseTable):
    print(count, end='\t\t')
    for i in j:
        print(i, end='\t')
    print()

# 输入测试串
print('\t\t\tTest')
while True:
    string = input("String (input 退出，退出程序):")
    if string=="退出":
        break
    string += '#'  # 输入串结尾加‘#’
    # 判断输入序列是否符合语法
    if parseString(rule, string):
        print("accepted")
    else:
        print("Not accepted")
# ------------------------------------------------------------------------
